#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;


 //Definition for singly-linked list.
 struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
  };

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* i = l1;
        ListNode* j = l2;
        ListNode* curr = new ListNode(0);
        ListNode* head = curr;
        while(i!=NULL&&j!=NULL){
            if(i->val<=j->val){
                curr->next = i;
                curr = i;
                i = i->next;
                curr->next = NULL;
            }
            else{
                curr->next = j;
                curr = j;
                j = j->next;
                curr->next = NULL;
            }
        }
        if(i!=NULL){
            curr->next = i;
        }
        if(j!=NULL){
            curr->next = j;
        }
        return head->next;
        
    }
};

int main(){
    Solution S;
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    ListNode* head2 = new ListNode(1);
    head2->next = new ListNode(3);
    head2->next->next = new ListNode(4); 
    ListNode* result = S.mergeTwoLists(head,head2);
    return 0;
}